﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.SlidingWindow
{
    /// <summary>
    /// LeetCode 567 题，Permutation in String，难度 Medium：
    /// </summary>
    public static class MinStrLen
    {
        /// <summary>
        /// 是否存在最小覆盖字串
        /// </summary>
        /// <param name="t">子字符串</param>
        /// <param name="s">父字符串</param>
        /// <returns></returns>
        public static bool checkInclusion(string t, string s)
        {
            Dictionary<char, int> windows = new Dictionary<char, int>();
            Dictionary<char, int> need = new Dictionary<char, int>();
            int valid = 0;
            //需要的字符用dic 表示
            foreach (var c in t) { need[c]++; }
            int left = 0, right = 0;
            while (right < s.Length)//注意[left,right)
            {
                char c = s[right];
                right++;
                if (need.ContainsKey(c))//当前的char就是需要的key 
                {
                    windows[c]++;
                    if (need[c] == windows[c])//证明当前字符cur 需要的数量已经满足了
                    {
                        valid++;
                    }

                }
                while (right - left >= t.Length)
                {
                    if (valid == need.Count)//判断当前的是否已经满足需求 
                    {
                        return true;
                    }
                    char d = s[left];
                    left++;
                    //窗口进行更新
                    if (need.ContainsKey(d))//当前字符是需要的字符
                    {
                        if (need[d] == windows[d])//证明当前字符cur 需要的数量已经满足了 但是我现在要去掉这个d，所以后面就不满足了
                        {
                            valid--;
                        }
                        windows[d]--;
                    }
                }
            }
            return false;
        }
        /// <summary>
        /// 如存在最小覆盖字串 就输出出来
        /// </summary>
        /// <param name="t">子字符串</param>
        /// <param name="s">父字符串</param>
        /// <returns></returns>
        public static string minWindow(string t, string s)
        {
            Dictionary<char, int> window = new Dictionary<char, int>();
            Dictionary<char, int> need = new Dictionary<char, int>();
            foreach (var c in s) { need[c]++; };
            int left = 0, right = 0, valid = 0, start = 0, len = int.MaxValue;
            while (right < s.Length)
            {

                char c = s[right];
                if (need.ContainsKey(c))
                {
                    window[c]++;
                    if (window[c] == need[c])
                    {
                        valid++;
                    }
                }
                while (need.Count == valid)//当前窗体已经满足要求  收缩看看
                {

                    if (right - left < len)//符合要求就给最小len 复制
                    {
                        start = left;
                        len = right - left;
                    }
                    char d = s[left];
                    left++;
                    if (need.ContainsKey(d))
                    {
                        if (valid == need.Count)
                        {
                            valid--;
                        }
                        window[d]--;
                    }
                }
            }
            return len == int.MaxValue ? "" : s.Substring(start, len);
        }

        /// <summary>
        /// 找所有字母异位词,
        /// 相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
        /// </summary>
        /// <param name="s">主</param>
        /// <param name="t">次</param>
        /// <returns></returns>
        public static List<int> findAnagrams(string s, string t)
        {
            Dictionary<char, int> window = new Dictionary<char, int>();
            Dictionary<char, int> need = new Dictionary<char, int>();
            foreach (var c in t) { need[c]++; };
            int left = 0, right = 0, valid = 0;
            List<int> res = new List<int>();
            while (right < s.Length)
            {
                char c = s[right];
                right++;
                if (need.ContainsKey(c))
                {
                    window[c]++;
                    if (need[c] == window[c])
                    {
                        valid++;
                    }
                }
                while (need.Count == valid)
                {
                    if (valid == need.Count)
                    {
                        res.Add(left);
                    }
                    char d = s[left];
                    left++;
                    if (need.ContainsKey(d))
                    {
                        if (window[d] == need[d])
                            valid--;
                        window[d]--;
                    }
                }
            }
            return res;
        }
        /// <summary>
        /// 最长无重复子串
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static int lengthOfLongestSubstring(string s)
        {
            Dictionary<char, int> window = new Dictionary<char, int>();
            int left = 0, right = 0,res=0;
            while (right<s.Length)
            {
                char c = s[right];
                right++;
                window[c]++;
                while (window[c]>1)
                {
                    char d = s[left];
                    left++;
                    window[d]--;
                }
                res = Math.Max(res,right-left);
            }
            return res;
        }
    }
}
